
#!/usr/bin/python
"""
This is a hashmap implementation written in python.  It has an open address 
collision policy using a linear probe.  It's implemented over a ctypes
fixed-size array, and the indexing is done by taking the modulus of the hash of the key
and the size of the table(array).  It has many of the important functions
that the hashmap in the java 6 API has, i.e. put, get, remove, clear etc.  The mappings
object variable keeps track of the number of key/value pairs in the hashmap. The key/value
pairs are stored in 'records', which are ctypes structures.  The default capacity of the hash
table array is 8, and it's doubled each time the load factor of 0.75 is exceeded.
"""
from ctypes import *

#Ctypes struct is the type that will be put in the hash table array, has key and
#value fields.
class record(Structure):
    _fields_=("key", py_object), ("value", py_object)
    
class hash_map:
    #Initialization method creates a ctypes array for the table, possibly add a capacity argument.
    def __init__(self):
        hash_list_type = record * 8
        self.hash_array = hash_list_type()
        self.mappings = 0

    #Put method makes an index out of a key and puts the corresponding value in that index.
    def put(self, key, value):
        index = hash(key) % len(self.hash_array)
        if(self.is_null(self.hash_array[index])):
            self.hash_array[index].key = key
            self.hash_array[index].value = value
            self.mappings += 1
        else:
            new_index = self.linear_probe(index)
            self.hash_array[new_index].key = key
            self.hash_array[new_index].value = value
            self.mappings += 1
        if((float(self.mappings) / float(len(self.hash_array))) > .75):
            self.resize()

    #Resize method, makes a new array that is double the size of original, and puts all the values
    #of the old array in the new one.  
    def resize(self):
        temp = []
        for i in range(0, len(self.hash_array)):
            if(not self.is_null(self.hash_array[i])):
                temp.append(self.hash_array[i])
        hash_list_type = record * (len(self.hash_array)*2)
        self.hash_array = hash_list_type()
        self.mappings = 0
        for i in range(0, len(temp)):
            self.put(temp[i].key, temp[i].value)
        
    #Method that takes a key as an argument and removes that key/value pair if it's found.  
    def remove(self, key):
        index = hash(key) % len(self.hash_array)
        if(not self.is_null(self.hash_array[index]) and self.hash_array[index].key == key):
            self.hash_array[index] = record()
            self.mappings -= 1
        else:
            current = index + 1
            while((self.is_null(self.hash_array[current]) or self.hash_array[current].key != key) and current!=index):
                current += 1
                if(current == len(self.hash_array)-1):
                    current = 0
            if(not self.is_null(self.hash_array[current]) and self.hash_array[current].key == key):
                self.hash_array[current] = record()
                self.mappings -= 1
        
        
    #Get method finds record that has the given key argument and returns the value
    #associated with that key.  Returns None keyword if key/value pair isn't there.    
    def get(self, key):
        index = hash(key) % len(self.hash_array)
        if(not self.is_null(self.hash_array[index]) and self.hash_array[index].key == key):
            return self.hash_array[index].value
        else:
            current = index + 1
            while(current != index):
                if(not self.is_null(self.hash_array[current]) and self.hash_array[current].key == key):
                    return self.hash_array[current].value
                if(current == len(self.hash_array)-1):
                    current = -1
                current += 1
            return None

    #Prints the key and value of each record in the hashmap to the console.
    def print_values(self):
        for i in range (0, len(self.hash_array)):
            if(not self.is_null(self.hash_array[i])):
                print self.hash_array[i].key, " -> ", self.hash_array[i].value
        print ""

    #Linear probe method for collisions; if a collision occurs, this method searches for the next
    #open index.
    def linear_probe(self, index):
        current = index + 1
        while(not self.is_null(self.hash_array[current]) and current != index):
            if(current == len(self.hash_array)-1 and current!=0):
                current = 0
            current +=1
        return current

    #Boolean method that checks if the key of a given record is NULL or has been
    #set to a valid py_object value. 
    def is_null(self, record):
        try:
            bool(record.key)
        except ValueError:
            return True
        else:
            return False
    
    #Method that clears the hashmap.  
    def clear(self):
        for i in range(0, len(self.hash_array)):
            if(not self.is_null(self.hash_array[i])):
                self.hash_array[i] = record()
                self.mappings = 0

    #Method returns the size(number of mappings) of the hashmap
    def mapping_size(self):
        return self.mappings
    
    #Method that returns true if there are no key-value mappings,
    #false otherwise.
    def is_empty(self):
        if self.mappings == 0:
            return True
        else:
            return False
    
    #Method that returns True if the hashmap contains a specified key.   
    def contains_key(self, key):
        index = hash(key) % len(self.hash_array)
        if(not self.is_null(self.hash_array[index]) and self.hash_array[index].key == key):
            return True
        else:
            current = index + 1
        while(current != index):
            if(not self.is_null(self.hash_array[index]) and self.hash_array[index].key == key):
                return True
            if(index == len(self.hash_array)-1):
                current = -1
        current += 1
        return False

    #Method that returns True if the hashmap contains the specified value.
    def contains_value(self, value):
        for i in range(0, len(self.hash_array)):
            if(not self.is_null(self.hash_array[i]) and self.hash_array[i].value == value):
                return True
            return False
        
#Main method to display hashmap functions in action.  
def main():
    hm = hash_map()
    hm.put('a','c')
    hm.put('c', 'f')
    hm.put('z', 'g')
    hm.print_values()
    print hm.get('z')
    print hm.contains_value('f')
    print hm.contains_key('z')
    hm.put("hey","there")
    hm.put("this","is")
    hm.put("a","hashmap")
    hm.put("lol","z")
    hm.print_values()
    print hm.contains_value("hashmap")
    print hm.contains_value("lol")
    hm.clear()
    print hm.mapping_size() 
main()
